//package work.rightAnswer;
//class TrieNode{
//    int pass;
//    int end;
//    TrieNode[] nexts;
//
//    public TrieNode(){
//        pass = 0;
//        end = 0;
//        nexts = new TrieNode[26];
//    }
//}
//
//class Trie {
//    TrieNode root;
//
//    public Trie(){
//        root = new TrieNode();
//    }
//
//
//    public void insert(String word) {
//        if(word==null){
//            return;
//        }
//        TrieNode node = root;
//        char[] words = word.toCharArray();
//        root.pass++;
//        for (int i = 0; i < words.length; i++) {
//            int num = words[i]-'a';
//            if(node.nexts[num]==null){
//                node.nexts[num]= new TrieNode();
//            }
//            node = node.nexts[num];
//            node.pass++;
//        }
//        node.end++;
//    }
//
//    public boolean search(String word) {
//        if(word==null){
//            return false;
//        }
//        TrieNode node = root;
//        char[] words = word.toCharArray();
//        for (int i = 0; i < words.length; i++) {
//            int num = words[i]-'a';
//            if(node.nexts[num]==null){
//                return false;
//            }
//            node = node.nexts[num];
//        }
//
//        if(node.end>0){
//            return true;
//        }
//        return false;
//    }
//
//    public boolean startsWith(String prefix) {
//        if(prefix==null){
//            return false;
//        }
//        TrieNode node =root;
//        char[] chars = prefix.toCharArray();
//        for (int i = 0; i < chars.length; i++) {
//            int num = chars[i]-'a';
//            if(node.nexts[num]==null){
//                return false;
//            }
//            node = node.nexts[num];
//        }
//        return true;
//    }
//}
//
